#include <iostream>
using namespace std;
#define N 5
int maze[N][N]={
    {0,1,0,0,0},
    {0,1,0,1,0},
    {0,0,0,0,0},
    {0,1,1,1,0},
    {0,0,0,1,0}
};
int direction[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int visited[N][N]={0};
void printPath(int path[N][N],int length){
    for(int i=0;i<length;i++){
        for(int j=0;j<length;j++){
            cout<<path[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

int dfs(int x,int y,int path[N][N]){
    if(x==N-1&&y==N-1){
        path[x][y]=9;
        printPath(path,N);
        return 1;
    }
    visited[x][y]=3;
    path[x][y]=6;

    for(int i=0;i<4;i++){
        int newX=x+direction[i][0];
        int newY=y+direction[i][1];

        if(newX>=0&&newX<N&&newY>=0&&newY<N&&maze[newX][newY]==0&&!visited[newX][newY]){
            if(dfs(newX,newY,path)){
                return 1;
            }
        }
    }

    path[x][y]=0;
    return 0;
}

int main(){
    int path[N][N]={0};
    if(!dfs(0,0,path)){
        cout<<"No path found!"<<endl;
    }
    return 0;
}